\documentclass{ctexart}
\usepackage{ctex}
\usepackage{cite}
\usepackage{float}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage[colorlinks,linkcolor=blue]{hyperref}
\usepackage{geometry}
\usepackage{hyperref}
\usepackage{amsfonts, amssymb}
\usepackage{url}
\usepackage{array}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{fontspec}

\setmonofont{Consolas}
\linespread{1.5}
\pagestyle{plain}
\geometry{a4paper, scale=0.9}

\ctexset{
    section={
		format+ = \zihao{-3} \heiti \raggedright,
		name = {,、},
		number = \chinese{section},
		beforeskip = 1.0ex plus 0.2ex minus .2ex,
		afterskip = 1.0ex plus 0.2ex minus .2ex,
		aftername = \hspace{0pt}
    },
    % subsection={
	% 	format+ = \zihao{4} \kaishu \raggedright,
	% 	number = \chinese{subsection},
	% 	name = {（,）},
	% 	beforeskip = 1.0ex plus 0.2ex minus .2ex,
	% 	afterskip = 1.0ex plus 0.2ex minus .2ex,
	% 	aftername = \hspace{0pt}
	% },
	% subsubsection={
	% 	format+ = \zihao{-4} \fangsong \centering,
	% 	number = \ttfamily\arabic{subsubsection},
	% 	name = {,.},
	% 	beforeskip = 1.0ex plus 0.2ex minus .2ex,
	% 	afterskip = 1.0ex plus 0.2ex minus .2ex,
	% 	aftername = \hspace{0pt}
	% }
}

\lstset{
    basicstyle          =   \sffamily,           % 基本代码风格
    keywordstyle        =   \bfseries,           % 关键字风格
    commentstyle        =   \rmfamily\itshape,   % 注释的风格，斜体
    stringstyle         =   \ttfamily,           % 字符串风格
    flexiblecolumns,                             % 别问为什么，加上这个
    numbers             =   left,                % 行号的位置在左边
    showspaces          =   false,               % 是否显示空格，显示了有点乱，所以不现实了
    numberstyle         =   \zihao{-5}\ttfamily, % 行号的样式，小五号，tt等宽字体
    showstringspaces    =   false,
    captionpos          =   t,                   % 这段代码的名字所呈现的位置，t指的是top上面
    frame               =   lrtb,                % 显示边框
    language            =   [ANSI]{C},
    breaklines          =   true,
}

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\lstset{ %
        backgroundcolor=\color{white},   % choose the background color
        basicstyle=\footnotesize\ttfamily,        % size of fonts used for the code
        columns=fullflexible,
        breaklines=true,                 % automatic line breaking only at whitespace
        captionpos=b,                    % sets the caption-position to bottom
        tabsize=4,
        commentstyle=\color{mygreen},    % comment style
        escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
        keywordstyle=\color{blue},       % keyword style
        stringstyle=\color{mymauve}\ttfamily,     % string literal style
        frame=single,
        rulesepcolor=\color{red!20!green!20!blue!20},
        % identifierstyle=\color{red},
        language=C++,
}

\title{\huge \textbf{《CSAPP阅读笔记》\\ 史煜鑫}}
\date{}

\begin{document}

    \begin{figure}
        \centering
        \vspace*{8\baselineskip}
        \includegraphics[scale=0.5]{Figures/封面1.png}
        \vspace*{4\baselineskip}
    \end{figure}
    
    \maketitle

    \begin{table}[htb]
        \LARGE
        \renewcommand\arraystretch{1.5}
        \begin{center}
            \begin{tabular}{ccc}
                最后编译日期： & \today \\ \cline{2-2}
            \end{tabular}
        \end{center}
    \end{table}

    \begin{center}
        本文档使用 \LaTeX{} 编写
    \end{center}

    \clearpage
    \tableofcontents
    
    本书\cite{csapp}的全称为《Computer Systems - A Programmer's Perspective》，第三版；Flag开始时间：2022年9月19日。

    本书起源于1998年的秋季，旨在从程序员的视角看待计算机系统，本书涵盖了包括链接、加载、进程、信号、性能优化、虚拟内存、IO、网络与并发编程，等。

    \clearpage
    \section{第1章：计算机系统漫游}

    介绍计算机系统的主要概念和主题。

    \begin{lstlisting}
    #include <stdio.h>

    int main() 
    {
        printf("hello, world\n");
        return 0;
    }
    \end{lstlisting}

    \subsection{信息就是位（bit） + 上下文}

    系统中的所有信息，包括磁盘文件、内存中的程序、内存中存放的用户数据、网络上传输的数据，都是由一串比特表示的，区分不同数据对象的唯一方法是我们读取到这些数据对象时的上下文；例如，不同的上下文中，一个同样的细节序列可能表示一个整数、一个浮点数、一个字符串或者机器指令。

    数字的机器表示与实际的整数和实数是不同的，它们是对真实值的有限近似，详情将在 \textbf{第2章} 中讲述。

    \subsection{程序被其他程序翻译成不同的格式}

    在Unix系统中，源文件到目标文件的转化，由编译器驱动程序完成：

    \begin{lstlisting}
        gcc -o hello hello.c
    \end{lstlisting}

    从源文件到可执行文件，共需经历4个阶段，执行这四个阶段的程序（预处理器、编译器、汇编器、链接器）一起构成了\textbf{编译系统（compilation system）}。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.6]{Figures/1-3.png}
        \caption{编译系统}
    \end{figure}

    \begin{enumerate}
        \item \textbf{预处理阶段：} 预处理器处理\#开头的命令，例如对于\#include命令，预处理器会读取对应的头文件，并插入到程序文本中。
        \item \textbf{编译阶段：} 将文本文件hello.i翻译为hello.s，包含一个汇编语言程序。
        \item \textbf{汇编阶段：} 汇编器将hello.s翻译为机器语言指令，生成一种叫做 \textbf{可重定位目标程序（relocatable object program）}的格式，结果保存在二进制文件hello.o中。
        \item \textbf{链接阶段：} printf函数会位于一个专门的预编译好的名为printf.o的目标文件中，链接器负责将printf.o合并到我们的hello.o文件中，生成一个可执行的目标文件，可以被加载到内存中并被执行。
    \end{enumerate}

    \subsection{了解编译系统如何工作是大有益处的}

    \begin{enumerate}
        \item 为了优化程序性能，我们确实需要了解一些机器代码以及编译器将不同的C语句转化为机器代码的方式。例如，switch和一系列if-else哪个更加高效？一个函数调用的开销有多大？while总比for更有效吗？指针引用比数组索引更加有效吗？为什么重新排列一下算术表达式中的括号就能让函数运行的更快？
        \item 有助于理解链接时出现的错误，以及一些诸如静态变量和全局变量的区别是什么？静态库和动态库的区别是什么？为什么有一些链接错误直到运行时才会出现？，这样的问题。
        \item 避免出现诸如缓冲区溢出错误这样的安全漏洞。
    \end{enumerate}

    \subsection{处理器读取并解释储存在内存中的指令}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.7]{Figures/1-4.png}
        \caption{一个典型系统的硬件组成}
    \end{figure}

    \begin{enumerate}
        \item \textbf{总线：} 贯穿整个系统的是一组被称为“总线”的电子管道，其携带信息字节并在各个部件之间传递，总线通常被设计成传送\textbf{定长}的字节块，称为\textbf{字（word）}，字中的字节数（字长）是一个基本的系统参数，即我们通常说的32位系统和64位系统。
        \item \textbf{I/O设备：} IO设备是系统与外部世界的联系通道，每一个IO设备都会通过一个\textbf{控制器}或者\textbf{适配器}与IO总线相连，控制器一般指的是IO设备本身或者主板芯片组，而适配器则是插在主板上的一张卡（例如显卡）。
        \item \textbf{主存：} 从物理上来讲，主存是一组动态随机存取存储器（DRAM），从逻辑上来讲，主存是一个线性的字节数组。主存是一个临时存储设备，在处理器执行程序时，用来存放程序和程序要处理的数据。
        \item \textbf{中央处理单元/处理器（CPU）} CPU是解释存储在主存中的指令的引擎，CPU的核心是一个大小为一个字的、被称为\textbf{程序计数器（PC）}的寄存器。PC存储着一个地址，指向主存中的某条机器语言指令。从系统通电到系统断电，CPU都在不停的执行PC指向的指令，然后更新PC。CPU的指令围绕着主存、寄存器文件、算术逻辑单元（ALU）进行。
    \end{enumerate}

    处理器的\textbf{指令集架构}和处理器的\textbf{微体系结构}：指令集架构描述的是每条机器代码指令的效果，微体系结构描述的是处理器实际上是如何实现的。

    从键盘输入命令之后，shell将其读入寄存器，然后放入主存：

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/1-5.png}
        \caption{从键盘读取命令}
    \end{figure}

    敲下回车之后，shell将执行一系列的指令来加载可执行文件，这个过程中会将可执行文件中的机器代码与数据从磁盘复制到主存。由于DMA的存在，数据可以直接从磁盘到达主存，不经过处理器。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/1-6.png}
        \caption{从磁盘加载可执行文件到主存}
    \end{figure}

    CPU开始执行主存中的指令：

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/1-7.png}
        \caption{输出字符串，从主存到显示器}
    \end{figure}

    \subsection{高速缓存至关重要}

    加快CPU的运行速度要比加快主存的运行速度要来的容易和便宜的多。

    \textbf{高速缓存存储器（memory cache），简称为cache或者高速缓存}，用于存放处理器近期会用到的信息。高速缓存一般使用\textbf{静态随机访问存储器（SRAM）}的硬件技术来实现。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.6]{Figures/1-8.png}
        \caption{高速缓存存储器}
    \end{figure}

    \subsection{存储设备形成层次结构}

    每个计算机系统中的存储设备都被组织成了一个\textbf{存储器层次结构}，在这个层次结构中，从上至下，设备的访问速度越来越慢，容量越来越大，单位造价也越来越便宜。

    存储器层次结构的主要思想是：上一层的存储器作为第一层存储器的高速缓存。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.6]{Figures/1-9.png}
        \caption{一个存储器层次结构的示例}
    \end{figure}

    \subsection{操作系统管理硬件}

    可以把操作系统看成是应用程序和硬件之间插入的一层软件，所有应用程序对硬件的操作尝试都必须通过操作系统。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.4]{Figures/1-10.png}
        \caption{计算机系统的分层视图}
    \end{figure}

    操作系统具有两个基本功能：

    \begin{enumerate}
        \item 防止硬件被失控的应用程序滥用。
        \item 向应用程序提供简单一致的机制，来控制复杂而通常又大不相同的低级硬件设备。
    \end{enumerate}

    操作系统将通过几个基本的抽象概念（\textbf{进程、虚拟内存、文件}）来实现以上两个基本功能。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.4]{Figures/1-11.png}
        \caption{操作系统提供的抽象表示}
    \end{figure}

    其中，文件是对IO设备的抽象表示，虚拟内存是对主存、磁盘、IO设备的抽象表示，进程则是对处理器、主存、IO设备的抽象表示。

    进程是操作系统对正在运行的程序的一种抽象，一个系统上可以运行多个进程，而每个进程都好像在独占的使用硬件。

    \textbf{并发运行}的概念，指的是一个进程的指令和另一个进程的指令是交错运行的，操作系统实现这种交错运行的机制被称为\textbf{上下文切换}。

    操作系统保持对进程运行进行的跟踪所需要的所有状态信息，被称为\textbf{上下文}。上下文信息包括，PC寄存器的当前值、寄存器文件的当前值、主存上的内容。对于单处理器系统来说，当操作系统决定要把控制权从当前进程转移到某个新进程的时候，就会进行\textbf{上下文切换}，即保存当前进程的上下文，恢复新进程的上下文，然后移交控制权给新的进程。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.6]{Figures/1-12.png}
        \caption{进程的上下文切换}
    \end{figure}

    从一个进程到另一个进程的切换，由操作系统的\textbf{内核（kernel）}进行管理，\textbf{内核是操作系统代码常驻主存的那一部分}。当应用程序需要操作系统的某些操作时，例如文件读写，应用程序就会执行一条特殊的\textbf{系统调用（system call）}指令，将控制权传递给内核，内核执行被请求的操作并返回结果给应用程序。内核不是一个独立的进程，而是\textbf{操作系统管理全部进程所使用的代码和数据结构的集合}。

    在现代系统中，一个进程实际上由多个被称为\textbf{线程}的执行单元组成，每个线程都运行在进程的上下文中，并共享同样的代码和全局数据。线程一般而言比进程更加高效，多线程之间共享数据也比多进程之间共享数据来的容易。

    \textbf{虚拟内存}是一个抽象概念，其为每一个进程提供了一个假象，即每个进程都在\textbf{独占的}使用主存。每个进程看到的内存都是一致的，被称为\textbf{虚拟地址空间}。

    下图【\ref{fig_1_13}】是Linux进程的虚拟地址空间，地址空间最上面的区域是留给操作系统中的代码和数据的，地址空间的底部用来存放用户进程定义的代码和数据。

    每个进程看到的虚拟地址空间由大量准确定义的区域构成，每个区域都有专门的功能。

    \paragraph{程序代码和数据}~{}

    对于所有进程来说，代码总是从同一固定位置开始，紧接着的是对应C全局变量的数据位置。代码和数据区在进程一开始运行时就被指定了大小。

    \paragraph{堆}~{}

    代码和数据区之后紧接着的是\textbf{运行时堆}，堆可以在运行时动态的进行扩展和收缩，例如在调用C语言标准库函数中的malloc和free时。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.6]{Figures/1-13.png}
        \caption{进程的虚拟地址空间（图中地址从下往上增大）}
        \label{fig_1_13}
    \end{figure}

    \paragraph{共享库}~{}

    共享库大致位于地址空间的中间，用于存放诸如C语言标准库和数学库这样的共享库的代码和数据。

    \paragraph{栈}~{}

    \textbf{用户栈}位于\textbf{用户}虚拟地址空间的顶部，用来实现函数调用。用户栈会像堆一样，在进程执行期间进行动态的扩展和收缩，具体地讲，在调用函数时扩展，在从函数返回时收缩。

    \paragraph{内核虚拟内存}~{}

    虚拟地址空间的最顶部为内核保留，该区域不允许用户进程进行读写和调用，对该区域的读写和调用只能由操作系统内核进行。

    虚拟内存的运作，需要硬件和操作系统软件之间精密复杂的交互，包括对CPU生成的每一个地址的硬件翻译。\textbf{虚拟内存运作的基本思想是，把一个进程的虚拟内存的内容储存在磁盘上，然后主存将作为磁盘的高速缓存。}

    \paragraph{文件}~{}

    \textbf{文件}本质上就是字节序列，计算机系统上的每个IO设备，都可以被看作是文件，Unix系统中的输入输出都是通过，对一组被称为\textbf{UnixIO}的系统函数的调用，来实现文件的读写的。

    文件是一个简单、精致，但是强大的概念，因为其提供了一个统一的视图，用来对待系统中可能出现的所有各式各样的IO设备，例如在无需了解具体技术的前提下，读写使用了不同技术的磁盘。

    \subsection{系统之间利用网络通信}

    如果从一个单独的系统的角度去看，\textbf{网络}可以被看作一个IO设备。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.6]{Figures/1-14.png}
        \caption{网络也是一种IO设备}
    \end{figure}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.6]{Figures/1-15.png}
        \caption{通过telnet命令，通过网络远程运行hello}
    \end{figure}

    \subsection{重要主题}

    系统不仅仅是硬件，系统是硬件和系统软件互相交织的集合体，他们必须共同协作以达到运行应用程序的最终目的。

    \paragraph{Amdahl定律}~{}

    Amdahl定律关心的是，对系统的某一部分进行性能提升所带来的影响，其主要思想是，当我们对系统的某个部分进行加速时，其对系统整体性能的影响取决于该部分的重要性和加速程度。

    假设，系统执行某应用程序需要的时间是 $ T_{old} $ ，系统某部分所需的执行时间占 $ T_{old} $ 的比例为 $ \alpha $ ，现在，该部分的性能提升了，提升的比例为 $ k $ ，即，原先该部分需要的时间为 $ \alpha T_{old} $ ，现在该部分需要的时间为 $ \frac{\alpha T_{old}}{k} $ ，所以，现在系统的总执行时间为：

    \begin{equation}
        T_{new} = (1 - \alpha) T_{old} + \frac{\alpha T_{old}}{k} = T_{old}[ (1 - \alpha) + \frac{\alpha}{k} ]
    \end{equation}

    可以计算得到，整体的提升比例为：

    \begin{equation}
        S = \frac{T_{old}}{T_{new}} = \frac{1}{(1 - \alpha) + \frac{\alpha}{k}}
    \end{equation}

    举例而言，当 $ \alpha = 0.6 $ ， $ k = 3 $ 时，$ S \approx 1.667 $ ，虽然系统的一大部分提升了3倍的性能，但是整体只提升了1.667倍的性能，这也就是Amdahl定律的主要观点：\textbf{要想显著的加速整个体统，必须对系统中的大部分进行加速}。

    \underline{\textbf{书里说这个定理居然用学生想提升GPA来举例子，虾仁猪心啊啊啊啊啊啊啊啊啊啊！!!!!!！！。}}

    习题1.1答案：1.25 $ \times $ ，301.8公里每小时。
    习题1.2答案： $ k = \frac{8}{3} \approx 2.667 $

    \paragraph{并发和并行}~{}

    术语\textbf{并发（concurrency）}是一个通用的概念，指一个同时具有多个活动的系统；术语\textbf{并行（parallelism）}指的是用并发来是一个系统运行得更快。并行可以在系统的多个抽象级上进行运用。

    \paragraph{线程级并发（进程层次的并发）}~{}

    使用线程，可以在一个进程中执行多个控制流，自从20世纪60年代出现了时间共享以来，计算机系统中就开始有了对并发执行的支持。对于\textbf{单处理器系统}，并发只能由处理器在多个任务之间快速来回切换来实现。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.4]{Figures/1-16.png}
        \caption{单核处理器、多核处理器、超线程}
    \end{figure}

    随着多核处理器和超线程（hyperthreading）的出现，\textbf{多处理器系统}开始变得常见，如上图所示。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.4]{Figures/1-17.png}
        \caption{多核处理器的组织架构，以4核处理器为例}
    \end{figure}

    多核处理器将多个CPU集成到同一个集成电路芯片上，如上图所示。

    超线程，也成为同时多线程（simultaneous multi-threading），是一项允许一个CPU执行多个控制流的技术。使用超线程技术的CPU的某些硬件拥有多个备份，例如程序计数器PC和寄存器文件，而某些硬件则只有一个备份，例如执行浮点算术运算的单元。使用了超线程技术的CPU，可以在\textbf{单个时钟周期}内，决定执行哪一个线程。

    \paragraph{指令级并行（较低抽象层次的并行）}~{}

    \textbf{指令级并行}指的是，现代处理器可以同时执行多条指令的属性。对于现代处理器而言，每个时钟周期可以处理多条指令，但是实际上，每条指令从开始到结束仍需经过若干时钟周期，但是现代处理器可以同时执行非常多的指令，使得平均而言，每个时钟周期可以完成多个指令。本书的后续章节，我们将研究流水线的使用。

    如果一个处理器可以达到比一个时钟周期完成一条指令更快的运行速度，就可以被称为\textbf{超标量（super-scalar）处理器}。

    \paragraph{单指令、多数据并行（最低层次的并行）}~{}

    许多现代处理器拥有特殊的硬件，允许一条指令产生多个可以并行执行的操作，这种方式被称为\textbf{单指令、多数据，即SIMD并行}。在第5章的网络旁注中，我们描述了使用编译器提供的特殊向量数据类型来编写程序，利用SIMD并行性的方式。

    \paragraph{计算机系统中，抽象的重要性}~{}

    \textbf{抽象的使用}是计算机科学中最为重要的概念之一。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.6]{Figures/1-18.png}
        \caption{计算机系统提供的一些抽象，计算机系统中的一个重大主题就是提供不同层次的抽象表示，用来隐藏实际实现的复杂性}
    \end{figure}

    例如，指令集是对实际处理器硬件的抽象；文件是对IO设备的抽象；虚拟内存是对程序存储器的抽象；进程是对一个正在运行的程序的抽象；虚拟机是对整个计算机的抽象。

    \clearpage
    \section{第2章：信息的表示和处理}

    主要讲述计算机的算术运算。

    ————————————————————

    我们需要方法来表示基本的数据类型，比如对整数和实数的近似值。

    我们需要考虑机器级的指令如何操作这样的数据。

    我们需要考虑编译器如何将C程序翻译为这样的指令。

    一旦理解了编译器和机器级代码，我们就能了解如何通过编写C程序以及编译它们来最大化程序的性能。

    本部分（第一部分：程序结构和执行，2、3、4、5、6章）以存储器子系统的设计作为结束，这是现代计算机系统最复杂的部分之一。

    ————————————————————

    我们研究三种最重要的数字表示，\textbf{无符号（unsigned）}编码基于传统的二进制表示法，表示大于等于0的数字；\textbf{补码（two's complement）}编码是表示有符号整数的最常见的方式；\textbf{浮点数（floating-point）}编码，是表示实数的科学计数法的以2为基数的版本。

    对于整数来说，计算机的表示法用有限的bit来表示一个数字编码，因此当结果太大以至于不能表示的时候，就会\textbf{溢出（overflow）}，同时，整数的计算机运算，满足正真的整数运算的许多性质，例如乘法结合律和乘法交换律（计算机可能没有产生预期的结果，但至少给出了一致的结果）。

    对于浮点数来说，溢出会产生特殊值 $ + \infty $ ，由于表示的精度有限，浮点运算是\textbf{不可结合}的。

    计算机的整数表示，只能表示一个相对小的范围，但是这种表示是精确的；计算机的浮点数表示，能够表示一个较大的数值范围，但是这种表示是近似的。

    通过直接操作数字的位级表示，我们得到了几种进行算术运算的方式，理解这些技术对于理解编译器产生的机器级代码是很重要的，\textbf{编译器会试图优化算术表达式求值的性能}。

    程序员需要对计算机运算与更为人熟悉的整数和实数运算之间的关系有更清晰的理解。

    本章中所有关于C的内容对C++都有效。

    C与Unix都由贝尔实验室研发，C语言开发的目的就是和Unix一起使用。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.6]{Figures/2-1.png}
        \caption{向GCC指定不同的C语言版本}
    \end{figure}

    本书中的C代码，主要基于ISO C90标准，但是也会包括一些C99、C11、C++的特性。

    \subsection{信息存储}

    绝大多数计算机使用字节（byte）作为最小的可寻址的内存单位。

    机器级程序将内存视为一个非常大的字节数组，称为\textbf{虚拟内存（virtual memory）}，内存中的每一个字节都有一个唯一的数字来标识，称为\textbf{地址（address）}，所有可能的地址的集合就被称为\textbf{虚拟地址空间（virtual address space）}。

    虚拟地址空间实际的实现，是将DRAM、闪存、磁盘存储器、特殊硬件、操作系统软件，结合起来，为机器级的程序提供了一个看上去统一的字节数组。

    C语言中的指针的值，无论是什么类型的指针，都指向虚拟地址空间中某个存储块的第一个字节的虚拟地址。

    C编译器，会在编译过程中，将每个指针和其类型信息联系起来，这样就可以根据类型，来生成不同的机器级代码，来访问存储在指针指向的位置的值；\textbf{但是，在C编译器生成的机器级代码中，并不会包含这个类型信息。}

    \paragraph{十六进制表示法（hexadecimal）}~{}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-2.png}
        \caption{图2-2：十六进制表示法}
    \end{figure}

    在C语言中，十六进制数字以“0x”或者“0X”开头，用“a-f”或者“A-F”来表示10-15，本书中，我们使用 $ 0x123ABC $ 或者 $ 123ABC_{16} $ 来表示十六进制数字。

    十六进制数字和十进制数字的相互转化：

    $$
        \begin{cases}
            314 \; 156 = 19 \; 636 \times 16 + 12 & (C) \\
            16 \; 934 = 1227 \times 16 + 2 & (2) \\
            1227 = 76 \times 16 + 11 & (B) \\
            76 = 4 \times 16 + 12 & (C) \\
            4 = 0 \times 16 + 4 & (4) \\
            \therefore 314 \; 156 = 4CB2C_{16}
        \end{cases}
    $$

    $$
        7AF_{16} = 7 \times 16^2 + 10 * 16 + 15 = 1967
    $$

    每台计算机都有一个\textbf{字长（word size）}，用来指明指针数据的\textbf{标称大小（nominal size）}，这也决定了虚拟地址空间的最大大小。使用GCC编译C代码程序时，使用参数“-m32”，或者“-m64”，就可以指定编译器为32位字长的机器，或者是为64位字长的机器生成机器代码。我们一般称之为，“32位程序”和“64位程序”（区别在于程序是如何编译的）。

    在C语言中，某些数据类型的确切字节数，取决于程序是如何被编译的，例如long在32位程序中为4字节，而在64位程序中为8字节。

    在ISO C99中，引入了一些大小固定的数据类型，不随编译器和机器设置变化，如int32\_t，int64\_t。

    程序员应该尽力使他们的程序在不同的机器和不同的编译器上可移植，可移植性的一个重要方面就是，程序对不同数据类型的确切大小，不敏感。

    对于需要跨越多个字节的对象，必须确定两点：1）这个对象的地址是什么？2）在内存中如何排列这些字节。

    在大多数机器上，多字节的对象都是连续存储的，对象的地址是所使用的字节中的最小地址。小端法（little endian）：最低有效字节在最前面。大端法（bid endian）：最高有效字节在最前面。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.55]{Figures/2-3.png}
        \caption{图2-3：基本C数据类型的典型大小}
    \end{figure}

    例如，对于32位整数，0x01234567，其地址为0x100，则：

    \begin{itemize}
        \item 大端法：01（0x100）、23（0x101）、45（0x102）、67（0x103）
        \item 小端法：67（0x100）、45（0x101）、23（0x102）、01（0x103）
    \end{itemize}

    有一些机器使用小端法，有一些机器使用大端法，还有一些机器是双端法（bi-endian），即可以将其配置成小端法，也可以将其配置成大端法。

    little endian与big endian这两个词语，出自《格列夫游记》。虽然有些处理器是双端的，但某些操作系统，例如IOS和Android，只能在小端法下运行。

    大部分情况下，程序员不需要关注大端法或者是小端法，但也有一小部分情况，例如通过网络传输二进制数据时，或者，阅读检查机器级程序时，或者，在编写一些系统级程序时，需要对指针使用强制类型转换（cast）。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.4]{Figures/2-4.png}
        \caption{图2-4，打印程序对象的字节表示}
    \end{figure}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.4]{Figures/2-5.png}
        \caption{图2-5，打印数据对象的字节表示}
    \end{figure}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.4]{Figures/2-6.png}
        \caption{图2-6，不同数据类型，不同平台上的字节表示}
    \end{figure}

    命令man acsii可以用来生成一张ASCII的字符码的表。

    Unicode编码，对于常见的字符会使用1字节或者2字节的编码，对于其他不常见的字符则会采用标准的4字节的编码。

    计算机系统的一个基本概念是，从机器的角度来看，程序仅仅只是字节序列。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-7.png}
        \caption{2-7：布尔代数的运算}
    \end{figure}

    布尔代数起源于1850年，George·Boole的工作，1937年香农在自己的硕士论文中表明了，布尔代数可以用来设计和分析机电继电器网络。布尔代数也可以由单个bit扩展到01向量，即位向量。

    \begin{itemize}
        \item 布尔运算 $~$，非，逻辑运算NOT，命题逻辑中用 $ \lnot $ 表示；
        \item 布尔运算 $\&$，与，逻辑运算AND，命题逻辑中用 $ \land $ 表示；
        \item 布尔运算 $|$，或，逻辑运算OR，命题逻辑中用 $ \lor $ 表示；
        \item 布尔运算 $\hat{}$，异或，逻辑运算XOR，命题逻辑中用 $ \oplus $ 表示；
    \end{itemize}

    当考虑长度为w的向量上的布尔运算时，我们会得到一种不同的数学形式，称之为布尔环（Boolean Ring）。

    位向量的一个很有趣的应用是用来表示集合（编码）。

    不要混淆C语言中的\textbf{逻辑运算}和\textbf{位运算}！

    逻辑运算有别于位运算的另一点是，如果逻辑运算的第一个参数求值就能确定整个表达式的结果，那么逻辑运算就不会对第二个参数进行求值（JAVA里似乎管这个叫短路？）。

    \textbf{逻辑右移}和\textbf{算数右移}：逻辑右移会在左端补零，算数右移会在左端补原来的最高有效位，算数右移在有符号整数的运算中非常有用。

    C语言标准并未明确定义，右移应该是算术右移还是逻辑右移，不过，绝大多数的编译器都将右移实现为算术右移。在JAVA中，明确规定“> >”表示算数右移，“> > >”表示逻辑右移。

    还有一个问题，当我们对一个长度为w的整数位移k位（$ k \ge w $）时，JAVA中明确规定，实际的位移长度为 $ k \; mod \; w $ ，而C语言中，对此并没有明确的规定，不过许多机器也会对位移量取模（包括我现在用的）。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.55]{Figures/2-8.png}
        \caption{2-8：整数的数据与算数操作属于，w表示位数}
    \end{figure}

    \subsection{整数表示}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-9.png}
        \caption{2-9：32位程上，C语言中整数类型数据的典型取值范围}
    \end{figure}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-10.png}
        \caption{2-10：64位程序上，C语言中整数类型数据的典型取值范围}
    \end{figure}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-11.png}
        \caption{C语言标准定义的每种语言类型必须保证的最小组织范围}
    \end{figure}

    Java只支持有符号数，C和C++默认为有符号数，支持无符号数。

    对于向量 $ \overrightarrow{x} = [x_{w - 1}, x_{w - 2}, \cdots, x_0] $ ，定义函数Binary to Unsigned：

    \begin{equation}
        B2U_w(\overrightarrow{x}) \doteq \sum_{i = 0}^{w - 1} x_i 2^i
    \end{equation}

    $ \doteq $ 表示，左边，被定义为，等于，右边。函数 $ B2U_w $ 是一个\textbf{双射}。

    在补码（two's-complement）的定义中，将字的最高有效位，解释为，负权（negative weight），定义函数，Binary to Two's-complement，来表示补码的定义：

    \begin{equation}
        B2T_w(\overrightarrow{x}) \doteq -x_{w - 1} 2^{w - 1} + \sum_{i = 0}^{w - 2} x_i 2^i
    \end{equation}

    最高有效位 $ x_{w - 1} $ 也被称为\textbf{符号位}，其权重为 $ -2^{w - 1} $ 。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-13.png}
        \caption{图 2-13}
    \end{figure}

    \begin{center}
        $ B2T_4([0001]) = 1 $

        $ B2T_4([0101]) = 5 $

        $ B2T_4([1011]) = -5 $

        $ B2T_4([1111]) = -1 $
    \end{center}

    补码所能表示的最小值是 $ [10 \cdots 0] $ ，即 $ -2^{w-1} $ ，补码所能表示的最大值是 $ [01 \cdots 1] $ ，即 $ 2^{w - 1} - 1 $ 。

    函数 $ B2T_w $ 同样是一个\textbf{双射}。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-14.png}
        \caption{图 2-14}
    \end{figure}

    \begin{center}
        $ |TMin_w| = |TMax_w| + 1 $

        $ UMax_w = 2 \times TMax_w + 1 $
    \end{center}

    \textbf{C语言标准并没有要求，使用补码，来表示有符号数，但是几乎所有的机器都是这么做的。}

    当C预处理器，遇到，仅使用空格或者其它空白字符，分隔的一个字符串常量序列时，会把它们串联起来。

    在打印，例如int32\_t和uint64\_t时，可以在，printf中使用\textbf{宏}，PRId32和PRIu64。

    使用这些宏，可以保证，无论代码是如何被编译的，都能够生成格式正确的字符串。

    -

    \textbf{反码（Ones'-Complement）}，相当于，最高有效位的权重，是 $ -(2^{w - 1} - 1) $ 而不是 $ -2^{w - 1} $ ，定义函数Binary to One's-complement：

    \begin{equation}
        B2O_w(\overrightarrow{x}) \doteq -x_{w - 1} (2^{w - 1} - 1) + \sum_{i = 0}^{w - 2}x_i2^i
    \end{equation}

    \textbf{原码（Sing-Magnitude）}，最高有效位是符号位：

    \begin{equation}
        B2S_w(\overrightarrow{x}) \doteq (-1)^{x_{w - 1}} \cdot (\sum_{i=0}^{w - 2} x_i 2^i)
    \end{equation}

    反码和原码，都会对数字0，产生两种表示，+0和-0，浮点数中会使用到原码。

    术语补码，来源于这样一个性质，对于非负数x，我们使用 $ 2^w - x $ 来计算 -x 的w位表示。

    术语反码，来源于这样一个性质，我们用 $ [111\cdots1] = x $ 来计算 -x的反码表示。

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-15.png}
        \caption{图 2-15 12345 和 -12345的补码表示，以及53191的无符号表示}
    \end{figure}

    对于大多数C语言的实现来说，有符号数和无符号数之间的转换，要从位级的角度，而不是数字的角度来看。\textbf{即，强制类型转换的结果，会保持位值不变，只改变解释这些位的方式。}

    补码向无符号数转换（Two's Complement to Unsigned）：

    \begin{equation}
        T2U_w(x) = \begin{cases}
            x + 2^w , & x < 0 \\
            x , & x \ge 0
        \end{cases}
    \end{equation}

    或者，也可以写成：

    \begin{equation}
        T2U_w(x) = x + x_{w - 1} 2^w
    \end{equation}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-16.png}
        \caption{图 2-16 w=4时的补码表示和无符号表示}
    \end{figure}

    无符号数向补码转换（Unsigned to Two's Complement）：

    \begin{equation}
        U2T_w(u) = \ \begin{cases}
            u, & u \le TMax_w \\
            u - 2^w, & u > TMax_w
        \end{cases}
    \end{equation}

    或者也可以直接写成：

    \begin{equation}
        U2T_w(u) = -u_{w - 1} 2^w + u
    \end{equation}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-17.png}
        \includegraphics[scale=0.5]{Figures/2-18.png}
        \caption{图 2-17、2-18，补码与无符号数之间的转换}
    \end{figure}

    总结一下就是，无符号数与有符号数之间的转换，如果是在范围内的，可以直接转换，如果是不在范围内的，需要加上或者减去 $ 2^w $ 。

    \textbf{C语言标准被没有指定有符号数的表示方式，但是大多数编译器都实现为补码表示。}

    \textbf{C语言标准并没有指定如何进行无符号数和有符号数之间的转换，但是大多数编译器都遵循底层的二进制表示不变的原则。}

    \textbf{在C语言中，当遇到同时有有符号数和无符号数的算术运算时，会将有符号数隐式转换为无符号数。}

    本人PC上的C++代码的表现和上述三点完全一致；

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-19.png}
        \caption{图 2-19，C语言的升级规则的效果}
    \end{figure}

    \paragraph{扩展一个数字的位表示}~{}

    不同字长的整数之间的转换。

    将无符号数转换成字长更长的类型，只需要在前面添加0，这种操作被称为\textbf{零扩展（zero extension）}。

    将有符号数转换为字长更长的类型，的操作，被称为\textbf{符号扩展（signed extension）}，公式定义如下：

    \begin{equation}
        \overrightarrow{x} = [{\color{blue} x_{w - 1} }, x_{w - 2}, \cdots, x_0]
    \end{equation}

    \begin{equation}
        \overrightarrow{x}' = [{\color{blue} x_{w - 1}}, {\color{blue} x_{w - 1}}, \cdots, {\color{blue} x_{w - 1}}, x_{w - 2}, \cdots, x_0]
    \end{equation}

    其中 $ w' > w $ ，则 $ B2T_w(\overrightarrow{x}) = B2T_{w'}(\overrightarrow{x'}) $ 。

    \begin{lstlisting}[language=C++, lineskip=3pt]
template <typename integer>
string to_binary_str(integer x) {
    string res(sizeof(integer) * 8, '0');
    int idx = 0;

    for (int i = 0; i < sizeof(integer) * 8; ++i) {
        if (x & 0x01u) res[sizeof(integer) * 8 - 1 - idx] = '1';
        idx += 1;
        x = x >> 0x01;
    }

    return res;
}

int main() {
    signed short x = -123;
    signed int xx = x;

    cout << to_binary_str(x) << endl;
    cout << to_binary_str(xx) << endl;
}

// OUtput
// 1111111110000101
// 11111111111111111111111110000101
    \end{lstlisting}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.5]{Figures/2-20.png}
        \caption{图 2-20 符号扩展图示}
    \end{figure}

    值得一提的是，在将补码表示的有符号数转换为二进制无符号数时，会先发生大小（即类型）的转换，再发生从有符号到无符号的转换。这个规则是C语言标准要求的。（Page56）

    \paragraph{截断数字（减少表示数字的位）}~{}

    \begin{lstlisting}[language=C++, lineskip=3pt]
int x = 51391;
cout << x << endl; // 51391
cout << integer_to_bin_str(x) << endl; // 00000000000000001100100010111111

short sx = x;
cout << sx << endl; // -14145
cout << integer_to_bin_str(sx) << endl; // 1100100010111111

int y = sx; // -14145
cout << y << endl;
cout << integer_to_bin_str(y) << endl; // 11111111111111111100100010111111
    \end{lstlisting}

    当一个w位的数字，被截断为k位的数字时，会直接丢弃掉高w-k位。截断一个数字，有可能会导致它的值改变（就如上面的示例代码一样），\textbf{这也是溢出的一种形式。}

    对无符号数进行截断，$ \overrightarrow{x}' $ 是 $ \overrightarrow{x} $ 被截断的结果，可以公式化如下：

    \begin{equation}
        x = B2U_w(\overrightarrow{x}), \qquad x' = B2U_k(\overrightarrow{x}'), \qquad x' = x \; mod \; 2^k
    \end{equation}

    对补码数值进行截断，$ \overrightarrow{x}' $ 是 $ \overrightarrow{x} $ 被截断的结果，可以公式化如下：

    \begin{equation}
        x = B2U_w(\overrightarrow{x}), \qquad x' = B2T_k(\overrightarrow{x}'), \qquad x' = U2T_k(x \; mod \; 2^k)
    \end{equation}

    \clearpage
    \section{第3章：程序的机器级表示}

    如何阅读C编译器生成的x86-64汇编代码。

    \clearpage
    \section{第4章：处理器体系结构}

    讲述基本的组合和时序逻辑。

    \clearpage
    \section{第5章：优化程序性能}

    通过使编译器能够生成更有效的机器代码来学习C语言。

    \clearpage
    \section{第6章：存储器层次结构}

    不同类型的RAM、ROM、磁盘和固态硬盘。

    \clearpage
    \section{第7章：链接}

    讲述静态链接与动态链接。

    \clearpage
    \section{第8章：异常控制流}

    从底层的硬件异常和中断，到并发进程的上下文切换。

    \clearpage
    \section{第9章：虚拟内存}

    虚拟内存如何工作以及虚拟内存的特性。

    \clearpage
    \section{第10章：系统级IO}

    讲述Unix的基本IO概念，标准IO的局限性。

    \clearpage
    \section{第11章：网络编程}

    如何使用套接字（socket）来实现客户端-服务器模型，并介绍超文本传输协议HTTP。

    \clearpage
    \section{第12章：并发编程}

    以Internet服务器为例介绍并发编程。

    \clearpage
    \bibliography{References}
    \bibliographystyle{unsrt}
    
\end{document}
